Mobile cellular operators are placing increasing demands on capacity in order to support greater numbers of subscribers and higher bit-rate services. The combination of these factors is placing increasing pressure on the restricted amount of available radio spectrum. It is also proving difficult to meet the quality of service (QoS) requirements of the range of services to be supported and to achieve uniform availability of these services throughout the area of the network.
In attempts to provide more efficient use of the available spectrum, and more uniform coverage of the network area, for higher rate services in particular, workers in this field have considered the use of ad hoc networking between mobile terminals, such that a terminal with a poor quality link to a base station can pass its signal to another mobile terminal, to which it has a better quality link, for onward transmission to the base station, either directly or via one or more other mobile terminals. Similarly, a terminal with a poor quality link from a base station can receive its signal from another mobile terminal, from which it has a better quality link, this terminal having itself received the signal from the base station, either directly or via one or more other mobile terminals. Thus the overall path to or from the base station is improved by introducing additional hops via one or more intermediate mobile terminals. This arrangement is sometimes referred to as a “multi-hop” network or “multi-hop” architecture.
A routing protocol is then required to determine the path that a given signal should take: in the uplink direction, this may either be directly from the source mobile terminal to the base station or indirectly using one or more intermediate hops via other terminals; and in the downlink direction, this may either be directly from the base station to the destination mobile terminal or indirectly using one or more intermediate hops via other terminals.
These other terminals, via which better quality paths to and or from the base station exist, will often be nearer to the base station. Geometric considerations suggest that the proportion of such terminals in a given cell is likely to be low: the number of such terminals in a given cell is likely to be relatively small in relation to the total number of terminals in the cell.
Where multiple hops are involved, via intermediate terminals, some of these terminals, having particularly good links to the base station, may become overloaded, as they will be included in the paths from a large number of source terminals. Similarly, in the downlink direction, where multiple hops are involved, via intermediate terminals, some of these terminals, having particularly good links from the base station, may become overloaded, as they will be included in the paths to a large number of destination terminals. This increases the probability of congestion occurring in the cell.
Congestion is evidenced by a failure of traffic to meet its QoS requirements. The traffic load at which congestion occurs is dependent on the specific QoS requirements of the individual traffic type, its precedence level and the mix of traffic in the network. Different traffic types will experience congestion at different traffic loads. It preferentially affects low precedence and delay sensitive traffic. It is undesirable, for example, for delay sensitive traffic to be queued behind delay tolerant traffic, as the delay tolerant traffic could cause the delay sensitive traffic to exceed its delay limit and hence fail to meet its QoS requirements.
The routing protocol therefore needs to be sensitive to traffic load in the network and to the Quality of Service requirements and precedence level of each traffic type, in addition to the network topology. Furthermore, because of the dynamic nature of the network, due to terminal mobility, the vagaries of the channel, and fluctuations in traffic load, the routing protocol must be capable of dynamically adapting with the network topology and the network state.
Several routing protocols have been proposed which attempt to balance the variables found in a typical network where between nodes representing a source and a destination of a path for communication traffic there are intermediate nodes which define links so that the path is defined by a concatenation of the links, such protocols employing algorithms that address the choosing of appropriate links through the network.
E. W. Djikstra, in a paper entitled “A note on two problems in connexion with graphs”, Numerische Methematiik, 1 269, 1959, and incorporated here by reference, proposed an algorithm (hereinafter referred to as Dijkstra's algorithm) which seeks to find a path following the shortest route through a network from the source to the destination node. The length of an individual link in the path is described by a “cost”, which is assigned by the network manager. The length of the path is then defined as the sum of this “cost” over all of the links that make up the path. Advantageously, such a least-cost-path algorithm is stable but, disadvantageously, all of the traffic from a given source to a given destination uses the same path, resulting in congestion at relatively low traffic loads, and there is no provision for discriminating between traffic of different types, having different QoS requirements and/or precedence levels. This can result in, for example, delay sensitive traffic being queued behind delay tolerant traffic, whereby the delay sensitive traffic fails to meet its QoS requirements.
Z. Wang and J. Crowcroft, in a paper entitled “Quality of service routing for supporting multimedia applications”, IEEE Journal on Selected Areas in Communications, 14 (7) 1228, September 1996, proposed routing algorithms based on Dijkstra's algorithm but making use of additional information regarding the current network state, rather than just a single link cost, pre-processed to form a subset to which a form of Dijkstra's algorithm can then be applied. The links through the network are classified according to bandwidth, and then, for each class, the least delay path is found by using delay, rather than cost, as the variable. Although this provides limited separation of the traffic classes, there is a tendency for paths following the least delay routes to become congested.
E. Aboelela and C. Douligeris, in a paper entitled “Fuzzy metric approach for routing in B-ISDN”, IEEE Int. Conf. on Comms. 1999 (ICC 99), 1 484, June 1999, proposed a routing algorithm which defines a fuzzy logic system to combine the available bandwidth and delay of each link in the path to form a “fuzzy cost” for the path, and to use this in Dijkstra's algorithm instead of the simple link costs. This approach has the merits of finding distinct routes for each traffic class, so that more of the network resources are brought into use. However, this modified definition of cost means that widely divergent routes can be found that use excessive amounts of network resources and this algorithm can therefore be inefficient.
Such routing protocols that adapt to the network state by use of measured network metrics to meet QoS and/or precedence requirements may for convenience be referred to as “QoS routing protocols” and effect “QoS routing”
It is well known that QoS routing protocols that are sensitive to, and adapt to, the network state can produce unstable solutions, such that the calculated route varies each time that the calculation is performed, often oscillating between two solutions in a process known as “route flap”. To briefly summarise the effect, when a measurement is made of the prevailing network conditions, a route is calculated accordingly, which may be called route “A”. Traffic is then directed along route A. The additional traffic load on route A changes the network state such that, when a new measurement is made and the routing calculation repeated, a different route is found, which may be called route “B”. Redirecting the traffic to route B restores the original network state such that the next measurement and subsequent calculation result in route A being found again. Thus the routing algorithm oscillates between paths following route A and route B as traffic is alternated between these routes in response to routing calculations. It will be appreciated that the same phenomenon may be experienced with more than two routes and although appearing less dramatic than a simple oscillation, is nevertheless wasteful of network resources as rapid and frequent changes in distribution of traffic in the network result in increased link state advertisements throughout the network that use up resources.
The basic Dijkstra's algorithm is not susceptible to route flap because it relies only on a fixed link cost as input. However, QoS sensitive routing algorithms, such as those proposed by Wang and Crowcroft and by Aboelela and Douligeris are susceptible.
From the above, it will be seen that there exists a requirement for a routing protocol that is capable of practical implementation not only to define paths that follow stable routes within a dynamically varying network for traffic of different types, having different QoS requirements and or precedence levels, but also capable of allocating such traffic to these routes in an efficient manner.
This invention relates to determination of routes in a network, such as a dynamic wireless network, a multi-hop cellular wireless network or an ad hoc wireless network, in which traffic of multiple types is present, each traffic type having different QoS requirements and or precedence level. It is assumed that the network topology is known, having been determined by a separate protocol, although it may be time varying. It is further assumed that the network state is varying, such that the available bandwidth and delay on each link are changing with time, for example, due to varying traffic load and/or to changes in the propagation conditions in the various radio channels.
One particular application envisaged is that of a mobile cellular network in which the mobile terminals in a given cell may communicate with one another in an ad hoc manner, possibly under the control of the base station in that cell, as in a “multi-hop” network, such that the path taken by signals between any given source mobile terminal and destination base station, or between source base station and any given destination mobile terminal, may involve one or more intermediate hops via other mobile terminals.
Although the background to the invention has been presented in the context of a mobile cellular network, it will be apparent to those skilled in the art that the invention is equally applicable to other networks exhibiting similar dynamic properties. One such additional example is where the nodes are connected by point-to-point radio links.
It is particularly suited to networks with high connectivity, where the number of possible links between nodes, for example, mobile terminals, is relatively high in comparison to the number of nodes, such that there are multiple possible paths between most source and destination pairs. This does not imply that every mobile terminal is connected to every other mobile terminal in multiple ways; rather, that more than one path, possibly involving intermediate mobile terminals, exists between any one mobile terminal and the base station.
However, it is applicable in general to a network including a source and a destination node and between them a plurality of intermediate nodes and possible paths via at least one of said intermediate nodes.